package com.johann.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class T3_LengthOfLongestSubstring {
    public static class Solution{
        // 方法一、暴力解法 O(N^3) O(N) Hashset
        public int lengthOfLongestSubstring01(String s){
            int len= s.length();
            if (len<=1) {
                return len;
            }
            int maxLen=1;
            for (int i = 0; i < len; i++) {
                for (int j = i+1; j < len; j++) {
                    if (allUnique(s,i,j)) {
                        maxLen = Math.max(j-i+1,maxLen);
                    }
                }
            }
            return maxLen;
        }
        private boolean allUnique(String s,int x,int  y){
            Set<Character> characterSet = new HashSet<>();
            for (int i = x; i <=y ; i++) {
                // 边检查
                if (characterSet.contains(s.charAt(i))) {
                    return false;
                }
                // 边填充
                characterSet.add(s.charAt(i));
            }
            return true;
        }
        // 方法二、滑动窗口（1）HashSet
        public int lengthOfLongestSubstring02(String s){
            int len= s.length();
            if (len<=1) {
                return len;
            }
            int maxLen=1;
            int left=0,right=0;
            // [a,b) 判断b在区间内有无重复，无的话[a,b]; 有重复的话，[b,
            // pwwkew
            Set<Character> windowSet = new HashSet<>();
            while (right<len){
                // 只要串里包含重复的字符，左边界右移，同时移除左边的元素
                while (windowSet.contains(s.charAt(right))) {
                    windowSet.remove(s.charAt(left));
                    left++;
                }
                maxLen=Math.max(right-left+1,maxLen);
                windowSet.add(s.charAt(right));
                right++;
            }
            return maxLen;

        }
        // 方法二、滑动窗口（2）HashMap
        public int lengthOfLongestSubstring03(String s){
            int len= s.length();
            if (len<=1) {
                return len;
            }
            int maxLen=1;
            int left=0,right=0;
            // [a,b) 判断b在区间内有无重复，无的话[a,b]; 有重复的话，[b,
            // pwwkew
            HashMap<Character,Integer> windowMap = new HashMap<>();
            while (right<len){
                // getOrDefault方法，取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
                Integer var1 = windowMap.getOrDefault(s.charAt(right), 0);
                left = Math.max(left,var1);
                maxLen=Math.max(right-left+1,maxLen);
                windowMap.put(s.charAt(right),right+1);
                right++;
            }
            return maxLen;

        }
        // 方法二、滑动窗口（3）int[128]
        public int lengthOfLongestSubstring04(String s){
            int len= s.length();
            if (len<=1) {
                return len;
            }
            int maxLen=1;
            int left=0,right=0;
            // [a,b) 判断b在区间内有无重复，无的话[a,b]; 有重复的话，[b,
            // pwwkew
            int [] asciiArr = new int[128];
            while (right<len){
                // getOrDefault方法，取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
                int val = asciiArr[s.charAt(right)];
                left = Math.max(left,val);
                maxLen=Math.max(right-left+1,maxLen);
                asciiArr[s.charAt(right)]=right+1;
                right++;
            }
            return maxLen;

        }
    }


    public static void main(String[] args) {
        String s="abba";
        System.out.println(new Solution().lengthOfLongestSubstring04(s));
    }

}
